package com.leecode.xiehf.page_01;

/**
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 * <p>
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * <p>
 * https://leetcode-cn.com/problems/swap-nodes-in-pairs/
 */
public class Solution_0024 {

    public static void main(String[] args) {
        Solution_0024 solution_0024 = new Solution_0024();
        ListNode result = solution_0024.swapPairs(
                new ListNode(1,
                        new ListNode(4,
                                new ListNode(5, new ListNode(6))))
        );
        while (result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }

    // 内存占用太大，new了节点对象
    public ListNode swapPairs1(ListNode head) {
        ListNode h = new ListNode(0);
        ListNode c = h;
        while (head != null && head.next != null) {
            c.next = new ListNode(head.next.val, new ListNode(head.val));
            c = c.next.next;
            head = head.next.next;
        }
        c.next = head;
        return h.next;
    }

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next.next;
        head.next.next = null;
        head = reverse(head);
        head.next.next = swapPairs(next);
        return head;
    }

    // 通过指针断开 减少对象创建
    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}

